/**
 * 判断是否有环
 */
export function hasCycle(edges: Array<any> | undefined): boolean {
  const dag = new DAG()
  edges?.forEach((item) => {
    dag.addEdge(item.source, item.target)
  })
  return dag.hasCycle()
}

interface GraphInterface {
  [name: string]: Array<string>
}

class DAG {
  graph: GraphInterface
  constructor() {
    this.graph = {}
  }

  addEdge(from: string, to: string) {
    if (this.graph[from] === undefined) {
      this.graph[from] = []
    }
    this.graph[from].push(to)
    return this
  }

  hasCycle() {
    const visited = {}
    const recStack = {}

    for (const vertex in this.graph) {
      if (this.hasCycleHelper(vertex, visited, recStack)) {
        return true
      }
    }
    return false
  }

  hasCycleHelper(vertex: string, visited: any, recStack: any) {
    if (recStack[vertex]) {
      return true
    }

    if (visited[vertex]) {
      return false
    }

    visited[vertex] = true
    recStack[vertex] = true

    const neighbours = this.graph[vertex]
    if (neighbours) {
      for (let i = 0; i < neighbours.length; i++) {
        if (this.hasCycleHelper(neighbours[i], visited, recStack)) {
          return true
        }
      }
    }

    recStack[vertex] = false
    return false
  }
}
